W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
A word composed of characters 0 and 1 is called a de Bruijn sequence of order if every -character word composed of zeroes and ones is its subword - that is a fragment of consecutive characters - of . An example of a de Bruijn sequence of order 3 is 0001011100.
A type two de Bruijn sequence of order is such a word of arbitrary length that each -character word composed of zeroes and ones is a subsequence - that is a fragment of not necessarily consecutive characters - of . An example of a type two de Bruijn sequence of order 3 is 00101101. As far as we know, Nicolaas Govert de Bruijn did not invent such sequences, but their definition is similar to the previous one, isn't it?
Let us consider a word composed only of zeroes and ones. How many digits (0 or 1, of course) have to be added at the end of for the word to become a type two de Bruijn sequence of order ?
The first line of the standard input contains two integers and (), separated by a single space. The second line contains an -character word composed only of digits 0 and 1 that does not contain any spaces.
The first and only line of the standard output should contain a single non-negative integer, denoting the minimal number of digits that need to be added at the end of the word for it to become a t.t.d.B.s. of order .
For the input data:
5 3 00101
the correct result is:
2
Explanation of the example: After adding the characters 01 we obtain the following t.t.d.B.s. of order : 0010101.
Task authors: Marek Cygan and Jakub Radoszewski.